package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 * 题解：https://leetcode.cn/problems/set-matrix-zeroes/solutions/669901/ju-zhen-zhi-ling-by-leetcode-solution-9ll7
 *
 * @author yulongTian
 * @create 2024-05-28 17:09
 */
public class Test18 {
    public static void main(String[] args) {
//        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        new Test18().setZeroes(matrix);
        System.out.println(Arrays.deepToString(matrix));
    }

    /**
     * 尝试空间复杂度 O(1)
     * 两个额外的变量 标记第一行和第一列是否含有0
     * 然后使用第一行和第一列代替O(m+n)方法中的标记数组
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {

    }

//    /**
//     * 尝试空间复杂度 O(m+n)
//     *
//     * @param matrix
//     */
//    public void setZeroes(int[][] matrix) {
//        int[] m = new int[matrix.length];
//        int[] n = new int[matrix[0].length];
//
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                if (matrix[i][j] == 0) {
//                    m[i] = 1;
//                    n[j] = 1;
//                }
//            }
//        }
//        for (int i = 0; i < m.length; i++) {
//            if(m[i]!=1){
//                continue;
//            }
//            for (int j = 0; j < matrix[0].length; j++) {
//                matrix[i][j] = 0;
//            }
//        }
//        for (int i = 0; i < n.length; i++) {
//            if(n[i]!=1){
//                continue;
//            }
//            for (int j = 0; j < matrix.length; j++) {
//                matrix[j][i] = 0;
//            }
//        }
//    }

//    /**
//     * 利用额外空间记录值为0的行和列    O(m+n)
//     * 通过
//     *
//     * @param matrix
//     */
//    public void setZeroes(int[][] matrix) {
//        List<int[]> zeroList = new ArrayList<>();
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                if (matrix[i][j] == 0) {
//                    zeroList.add(new int[]{i, j});
//                }
//            }
//        }
//        for (int[] ints : zeroList) {
//            for (int i = 0; i < matrix[0].length; i++) {
//                matrix[ints[0]][i] = 0;
//            }
//            for (int j = 0; j < matrix.length; j++) {
//                matrix[j][ints[1]] = 0;
//            }
//        }
//    }

}
